In the prior art, data that is transmitted over wires frequently incurs errors, i.e. a binary 1 is distorted to appear as a binary 0 or vice versa. The errors may be single bit errors, where one bit in the data stream is corrupted, or double bit errors, where two bits in the data stream are corrupted. Note that typically, the data is transmitted over a set of wires, rather than a single wire, however errors could occur in both single wire and multiple wire transmission systems. Furthermore, the data is much longer than the number of wires, and thus is sent over multiple cycles, e.g. 16 wires are cycled 4 times to send 64 bits. Therefore, errors may occur over multiple cycles. In some systems, the data is packetized, which means that the data is delivered in specifically sized data packets. Thus, errors could occur in different data packets. One of the typical causes of errors is wire failures. Shorts or breaks in the wire can cause faulty signals to be sent down the wire. These failures are classified as one of two types. The first type is where the wire is either stuck-at-one or stuck-at-zero. Thus, whatever the input, the wire relays only a one (for stuck-at-one) or zero (for stuck-at-zero), and does not switch the signal. The second type is a malicious failure. This type of failure is where the output of the wire is switching, regardless of the input. For example, where the input is a zero, the wire output could be either a one or zero and where the input is a one, the wire output could be either a one or zero. In other words, the behavior of the wire is unpredictable. Furthermore, the error may be masked, because the wire failure may deliver the correct result.
To detect such errors, ECC code is transmitted along with the data. Cyclic codes are a type of ECC code that possess the capability to detect wire failures. Cyclic codes are an important class of codes. The generator/parity matrix for these codes are formed by the cyclic shift of a row. There are efficient cyclic codes for detection/correction of multiple random errors, byte errors and burst errors. Cyclic codes are discussed further in “Error Control Coding for Computer Systems” by T. R. N., Rao and E. Fujiwara, Prentice Hall, Englewood Cliffs, N.J. 07632, ISBN 0-13-28395-9, which is hereby incorporated by reference. Cyclic codes are directed at detecting malicious failures, and thus assume failures are malicious failures. Since the cyclic codes target for the latter, they require more bits than checking for stuck-at-fault failures, and the required number of bits may be more than a designer may have to spare. For example, assume a data message comprises 32 bytes, which is 256 bits. To allow for single bit error and double bit error detection 10 extra bits are required, the single error correction requires 9 bits, since 29 is the smallest power of 2 that is greater than (256+9). The 10th bit is used for detecting double bit errors, for a total of 266 bits. Thus, 10 bits are required for doing single error correction and double error detection. If these 266 bits are going to be transported across 10 wires, then 6 wires would carry 27 bits, and 4 wires would carry 26 bits. Thus, a wire failure could affect up to 27 bits. To detect malicious wire failures, 27 additional bits are required, see Theorem 3.7 from the book by Rao and Fujiwara, wherein a cyclic code generated by g(x) (of degree γ) can detect any burst of length γ or less. This will detect a wire failure plus any burst of length 27 or less extending over two consecutive wires, for a total of 293 bits. Thus, a total of 37 bits are required for error detection. This is a large amount of overhead which will consume a great proportion of system resources for transmission.
While 37 bits represents only 13% of 293 bits, a higher percentage of overhead may result from the extra bits needed for error detection, particularly when the data is transmitted in blocks or packets. For example, suppose a block of data comprises 7 cycles of data across 10 wires, for a total of 70 bits per block. Then 256 bits would require four blocks (3.6 blocks rounded up), while 293 bits would require five blocks (4.1 blocks rounded up). Thus, error detection would require an extra block or 20%.
In addition to adding overhead for data transmission, cyclic codes are more complex to implement. Decoding on the receiving end is complicated as many different mechanisms exist for implementing cyclic codes.
Therefore, there is a need in the art for error detection mechanism that detects wire stuck-at-faults which does not require significant overhead and is easy to implement.